import java.util.LinkedList;

public class maxChunksToSorted {
    /**
 * 计算将数组分割成块后，最多可以有多少块能够保持排序状态
 * 该方法通过使用一个栈来追踪数组中的最大值，从而确定可以保持排序的块的数量
 *
 * @param arr 输入的整数数组，代表待排序的序列
 * @return 返回数组分割成的最多排序块的数量
 */
public int maxChunksToSorted(int[] arr) {
    // 使用链表作为栈，来追踪每个块的最大值
    LinkedList<Integer> stack = new LinkedList<Integer>();
    for(int num : arr) {
        // 当栈不为空且当前元素小于栈顶元素时，说明当前元素打破了现有的排序状态
        if(!stack.isEmpty() && num < stack.getLast()) {
            // 记录当前块的最大值
            int head = stack.removeLast();
            // 移除所有比当前元素大的栈顶元素，因为这些元素不能和当前元素形成排序块
            while(!stack.isEmpty() && num < stack.getLast()) stack.removeLast();
            // 将当前块的最大值重新放入栈中，代表这个块可以保持排序
            stack.addLast(head);
        }
        // 如果栈为空或当前元素大于等于栈顶元素，当前元素可以形成一个新的排序块
        else stack.addLast(num);
    }
    // 栈的大小代表了可以保持排序的块的数量
    return stack.size();
}

}
